/**
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
*/

class Solution {
    List<List<Integer>> res=new ArrayList();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        for(int i=0;i<=nums.length;i++){
            boolean [] visited=new boolean[nums.length];

            dfs(i,0,nums,new ArrayList<Integer>(),visited);
        }
        return res;

    }
    public void dfs(int n,int start,int[]nums,List<Integer> path,boolean[]visited){
        if(n==path.size()){
            res.add(new ArrayList(path));
            return;
        }
       
        for(int i=start;i<nums.length;i++){
            if(i>start && nums[i]==nums[i-1] && !visited[i]){
                 continue;
            }
            visited[i]=true;
            path.add(nums[i]);
            dfs(n,i+1,nums,path,visited);
            path.remove(path.size()-1);
            visited[i]=false;
        }
}
}